﻿#include "Aho–Corasick.h"
#include <iostream>
#include <queue>
#include <vector>
#include <map>
using namespace std;

void AhoCorasick::addWord(int index) {
	string word=dictionary[index];
	 int len = word.length();
	 Node* currentNode = root;  
	 for ( int i = 0; i <len; ++i ) {
		 int charIndex = word[i] - 'a'; //индекс в массиве латинских букв
		 if ((charIndex < 0) || (charIndex > A_SIZE - 1)) {
			 string error = "The word \"";
			 error.append(word);
			 error.append("\"contains symbols which are not in alphabet."); 
			 throw new std::exception( error.c_str() );
		 }
                
        if (currentNode->go[charIndex] == 0) { // если еще нет перехода по этой букве, то созадем новый узел
			currentNode->go[charIndex] = new Node;
        }
        // переходим по букве в следующий узел
        currentNode = currentNode->go[charIndex];
    }
    currentNode->leafPatternNumber.push_back(index); // добавляем слово в массив слов, которым соответствует эта вершина
	currentNode->leaf=true; // вершина лист
}

void AhoCorasick::buildAutomat() {
	if (root!=0) {
		deleteNode(root);
	}
	queue<Node*> queue;
    root = new Node;
	root->suffLink = root;

	// добавляем слова в бор

	int size=dictionary.size();
	for ( int i = 0; i < size; ++i ) {
		addWord(i);
	}

	// задаем суффиксные ссылки для узлов, в которы переходим из корня
	
	for ( int i=0; i<A_SIZE; ++i ) {
		if ( root->go[i] != 0 ) {
			root->go[i]->suffLink = root;
			queue.push(root->go[i]);
		} else {
			root->go[i] = root;
		}
	}
	

	// запускаем для присвоения значений суффиксным ссылкам
	while ( !queue.empty() ) {
		Node* currentNode = queue.front();
		queue.pop();
		
		// вычисляем для потомков, так как для вершины вычислено на одном из предыдущих шагов
		for ( int i=0; i<A_SIZE; i++ ) {
			if ( currentNode->go[i]!=0 ) {
				Node* childNode = currentNode->go[i];
				queue.push(childNode);
				Node* suff = currentNode->suffLink;

				// суффиксный предок, у которого есть ребро по нужному символу
				while ( suff->go[i] == 0 ) {
					suff = suff->suffLink;
				}
				childNode->suffLink = suff->go[i];
				
				// сливаем массивы соответтсвущих слов
				childNode->leafPatternNumber.insert( childNode->leafPatternNumber.begin(), childNode->suffLink->leafPatternNumber.begin(), childNode->suffLink->leafPatternNumber.end());
			}
		}
	}
}

void AhoCorasick::search(map<int, vector<int>>& matches, string inputLine, string& outputLine) {
	if ( root==0 ) {
		throw new exception("Trie is empty");
	}
	int len= inputLine.length();
	Node* currentNode = root; 
	
	for (int i=0; i<len; i++) {
		outputLine += inputLine[i]; 
		int charIndex=inputLine[i] - 'a';
		if ((charIndex < 0) || (charIndex > A_SIZE - 1)) {
			charIndex=inputLine[i] - 'A';
			if ((charIndex<0) || (charIndex>A_SIZE - 1)) {
				currentNode = root; 
				continue; // неподходяший символ
			}
		}
		
		// переход в нужное состояние по данному символу
		while (currentNode->go[charIndex]==0) {
			currentNode = currentNode->suffLink;
		}
		currentNode = currentNode->go[charIndex];
		if (currentNode->leaf) {
			for (vector<int>::iterator itr=currentNode->leafPatternNumber.begin(); itr!=currentNode->leafPatternNumber.end(); itr++ ) {
				int beginIndex = i - dictionary[*itr].length() + 1;
				matches[*itr].push_back(beginIndex);
				for ( int j = beginIndex; j < beginIndex + dictionary[*itr].length(); ++j ) {
					outputLine[j] = '*';
				}
			}
		}
	}
}


void AhoCorasick::deleteNode(Node* node) {
	if (node == 0) {
		return;
	} 
    for ( int i = 0; i < A_SIZE; ++i ) {
		if ((node->go[i]!=0) && ( node->go[i]!=node )) {
			delete node->go[i];
		}
	}
	if (node != 0) {
		delete node;
	}
}